import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 25397
 * Date: 2022-01-23
 * Time: 17:23
 */
public class TopK {
    //求数组当中的前k个最大元素——建小堆
    //求数组当中的前k个最小元素——建大堆

    //这里以求前k个最小元素为例——建大堆
    public static int[]topK(int[] array,int k){
        //1.创建一个大小为k的大根堆
        PriorityQueue<Integer> maxHeap=new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });

        //2.遍历数组当中的元素，前k个元素放到队列中
        for(int i=0;i< array.length;i++){
            if(maxHeap.size()<k){//放k个
                maxHeap.offer(array[i]);
            }else {
                //3.从第k+1个元素开始
                //  每个元素与堆顶元素比较
                int top=maxHeap.peek();
                if(top>array[i]){
                    //先弹出，后存入
                    maxHeap.poll();
                    maxHeap.offer(array[i]);
                }

            }
        }
        int[]tmp=new int[k];
        for(int i=0;i<k;i++){
            tmp[i]=maxHeap.poll();
        }
        return tmp;
    }
    public static void main(String[] args) {
        int []array={18,21,8,10,34,12};
        int []tmp=topK(array,3);
        System.out.println(Arrays.toString(tmp));//[12, 10, 8]
    }
}
